/*
 * @lc app=leetcode.cn id=239 lang=golang
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start

import "container/heap"

// 使用大顶堆
type node struct {
	index, val int
}
type Heap []node

func (h Heap) Less(i, j int) bool {
	return h[i].val > h[j].val
}

func (h Heap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
func (h Heap) Len() int {
	return len(h)
}

func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(node))
}

func (h *Heap) Pop() interface{} {
	old := *h
	v := old[len(old)-1]
	*h = old[:len(old)-1]
	return v
}
func maxSlidingWindow(nums []int, k int) []int {
	h := Heap{}
	n := len(nums)
	for i := 0; i < k && i < n; i++ {
		heap.Push(&h, node{i, nums[i]})
	}

	res := make([]int, 0, n-k+1)
	res = append(res, h[0].val)
	for i, j := 1, k; j < n; i, j = i+1, j+1 {
		heap.Push(&h, node{j, nums[j]})
		for len(h) > 0 && h[0].index < i {
			heap.Pop(&h)
		}
		if len(h) > 0 {
			res = append(res, h[0].val)
		}

	}
	return res
}

// @lc code=end
